Discriminant Laplacian Embedding.

Multi%2DLabel Classification Inconsistency and Class Balanced K%2DNearest Neighbor.

Exploiting user interests for collaborative filtering interests expansion via personalized ranking.

Image Categorization Using Directed Graphs.

Multi%2Dlabel Feature Transform for Image Classifications.

Multi%2Dlabel Linear Discriminant Analysis.

Improved MinMax Cut Graph Clustering with Nonnegative Relaxation.

Directed Graph Learning via High%2DOrder Co%2Dlinkage Analysis.

Collaborative Filtering Weighted Nonnegative Matrix Factorization Incorporating User and Item Graphs.

Bridging Domains with Words Opinion Analysis with Matrix Tri%2Dfactorizations.

Closed form solution of similarity algorithms.

Feature subset non%2Dnegative matrix factorization and its applications to document understanding.

Convex and Semi%2DNonnegative Matrix Factorizations.
We present several new variations on the theme of nonnegative matrix factorization (NMF). Considering factorizations of the form X = F G T, we focus on algorithms in which G is restricted to contain nonnegative entries, but allow the data matrix X to have mixed signs, thus extending the applicable range of NMF methods. We also consider algorithms in which the basis vectors of F are constrained to be convex combinations of the data points. This is used for a kernel extension of NMF. We provide algorithms for computing these new factorizations and we provide supporting theoretical analysis. We also analyze the relationships between our algorithms and clustering algorithms, and consider the implications for sparseness of solutions. Finally, we present experimental results that explore the properties of these new methods. 1
Binary matrix factorization for analyzing gene expression data.

Convex and Semi%2DNonnegative Matrix Factorizations.
We present several new variations on the theme of nonnegative matrix factorization (NMF). Considering factorizations of the form X = F G T, we focus on algorithms in which G is restricted to contain nonnegative entries, but allow the data matrix X to have mixed signs, thus extending the applicable range of NMF methods. We also consider algorithms in which the basis vectors of F are constrained to be convex combinations of the data points. This is used for a kernel extension of NMF. We provide algorithms for computing these new factorizations and we provide supporting theoretical analysis. We also analyze the relationships between our algorithms and clustering algorithms, and consider the implications for sparseness of solutions. Finally, we present experimental results that explore the properties of these new methods. 1
Proceedings of the 2nd ACM SIGKDD Workshop on Data Mining using Matrices and Tensors

Symmetric two dimensional linear discriminant analysis %282DLDA%29.

K%2DSubspace Clustering.
Abstract. The widely used K-means clustering deals with ball-shaped (spherical Gaussian) clusters. In this paper, we extend the K-means clustering to accommodate extended clusters in subspaces, such as lineshaped clusters, plane-shaped clusters, and ball-shaped clusters. The algorithm retains much of the K-means clustering flavors: easy to implement and fast to converge. A model selection procedure is incorporated to determine the cluster shape. As a result, our algorithm can recognize a wide range of subspace clusters studied in various literatures, and also the global ball-shaped clusters (living in all dimensions). We carry extensive experiments on both synthetic and real-world datasets, and the results demonstrate the effectiveness of our algorithm. 1
Non%2Dnegative Laplacian Embedding.

Label Propagation on K%2Dpartite Graphs.

Consensus group stable feature selection.
Stability is an important yet under-addressed issue in feature selection from high-dimensional and small sample data. In this paper, we show that stability of feature selection has a strong dependency on sample size. We propose a novel framework for stable feature selection which first identifies consensus feature groups from subsampling of training samples, and then performs feature selection by treating each consensus feature group as a single entity. Experiments on both synthetic and real-world data sets show that an algorithm developed under this framework is effective at alleviating the problem of small sample size and leads to more stable feature selection results and comparable or better generalization performance than state-of-the-art feature selection algorithms. Synthetic data sets and algorithm source code are available at
Integrated KL %28K%2Dmeans %2D Laplacian%29 Clustering A New Clustering Approach by Combining Attribute Data and Pairwise Relations.

Knowledge transformation for cross%2Ddomain sentiment classification.

Dimension Reduction Techniques for Clustering.
Abstract. In this paper, we compare performance of several dimension reduction techniques, namely SVD, NMF and SDD.The qualitative comparison is evaluated on a collection of bars. We compare the quality of these methods from on the base of the visual impact. We also compare dimension reduction techniques SVD and HO-SVD on tensors- 3D bars. 1
Are Tensor Decomposition Solutions Unique%3F On the global convergence of HOSVD and ParaFac algorithms

Robust tensor factorization using R1 norm.

KDD2009 workshop report DMMT%2709 data mining using matrices and tensors.

Robust tensor factorization using R1 norm.

Tensor reduction error analysis %2D Applications to video compression and classification.
Tensor based dimensionality reduction has recently been extensively studied for computer vision applications. To our knowledge, however, there exist no rigorous error analysis on these methods. Here we provide the first error analysis of these methods and provide error bound results similar to Eckart-Young Theorem which plays critical role in the development and application of singular value decomposition (SVD). Beside performance guarantee, these error bounds are useful for subspace size determination according to the required video/image reconstruction error. Furthermore, video surveillance/retrieval, 3D/4D medical image analysis, and other computer vision applications require particular reduction in spatio-temporal space, but not along data index dimension. This motivates a D-1 tensor reduction. Standard method such as high order SVD (HOSVD) compress data in all index dimensions and thus can not perform the classification and pattern recognition tasks. We provide algorithm and error bound analysis of the D-1 factorization for spatio-temporal data dimensionality. Experiments on video sequences demonstrate our approach outperforms the previous dimensionality deduction methods for spatiotemporal data. 1.
Simultaneous tensor subspace selection and clustering the equivalence of high order svd and k%2Dmeans clustering.

Stable feature selection via dense feature groups.
Many feature selection algorithms have been proposed in the past focusing on improving classification accuracy. In this work, we point out the importance of stable feature selection for knowledge discovery from high-dimensional data, and identify two causes of instability of feature selection algorithms: selection of a minimum subset without redundant features and small sample size. We propose a general framework for stable feature selection which emphasizes both good generalization and stability of feature selection results. The framework identifies dense feature groups based on kernel density estimation and treats features in each dense group as a coherent entity for feature selection. An efficient algorithm DRAGS (Dense Relevant Attribute Group Selector) is developed under this framework. We also introduce a general measure for assessing the stability of feature selection algorithms. Our empirical study based on microarray data verifies that dense feature groups remain stable under random sample hold out, and the DRAGS algorithm is effective in identifying a set of feature groups which exhibit both high classification accuracy and stability.
Weighted Consensus Clustering.
Consensus clustering has emerged as an important extension of the classical clustering problem. We propose weighted consensus clustering, where each input clustering is weighted and the weights are determined in such a way that the final consensus clustering provides a better quality solution, in which clusters are better separated comparing to standard consensus clustering. Theoretically, we show that a reformulation of the wellknown L1 regularization LASSO problem is equivalent to the weight optimization of our weighted consensus clustering, and thus our approach provides sparse solutions which may resolve the difficult situation when the input clusterings diverge significantly. We also show that the weighted consensus clustering resolves the redundancy problem when many input clusterings correlate highly. Detailed algorithms are given. Experiments are carried out to demonstrate the effectiveness of the weighted consensus clustering.
Knowledge transformation from word space to document space.

Multi%2Ddocument summarization via sentence%2Dlevel semantic analysis and symmetric matrix factorization.
Multi-document summarization aims to create a compressed summary while retaining the main characteristics of the original set of documents. Many approaches use statistics and machine learning techniques to extract sentences from documents. In this paper, we propose a new multi-document summarization framework based on sentence-level semantic analysis and symmetric non-negative matrix factorization. We first calculate sentence-sentence similarities using semantic analysis and construct the similarity matrix. Then symmetric matrix factorization, which has been shown to be equivalent to normalized spectral clustering, is used to group sentences into clusters. Finally, the most informative sentences are selected from each group to form the summary. Experimental results on DUC2005 and DUC2006 data sets demonstrate the improvement of our proposed framework over the implemented existing summarization systems. A further study on the factors that benefit the high performance is also conducted.
Posterior probabilistic clustering using NMF.

On the equivalence between Non%2Dnegative Matrix Factorization and Probabilistic Latent Semantic Indexing.

Efficient Parallel I%2FO in Community Atmosphere Model %28CAM%29.

Efficient Parallel I%2FO in Community Atmosphere Model %28CAM%29.

KDD2008 workshop report DMMT%2708 data mining using matrices and tensors.

KDD2008 workshop report DMMT%2708 data mining using matrices and tensors.

A Two%2DStage Gene Selection Algorithm by Combining ReliefF and mRMR.
Abstract—Gene expression data usually contains a large number of genes, but a small number of samples. Feature selection for gene expression data aims at finding a set of genes that best discriminate biological samples of different types. In this paper, we present a two-stage selection algorithm by combining ReliefF and mRMR: In the first stage, ReliefF is applied to find a candidate gene set; In the second stage, mRMR method is applied to directly and explicitly reduce redundancy for selecting a compact yet effective gene subset from the candidate set. We also perform comprehensive experiments to compare the mRMR-ReliefF selection algorithm with ReliefF, mRMR and other feature selection methods using two classifiers as SVM and Naive Bayes, on seven different datasets. The experimental results show that the mRMR-ReliefF gene selection algorithm is very effective. Index Terms—Gene selection algorithms, reliefF, mRMR, mRMR-reliefF.
Binary Matrix Factorization with Applications.
An interesting problem in Nonnegative Matrix Factorization (NMF) is to factorize the matrix X which is of some specific class, for example, binary matrix. In this paper, we extend the standard NMF to Binary Matrix Factorization (BMF for short): given a binary matrix X, we want to factorize X into two binary matrices W,H (thus conserving the most important integer property of the objective matrix X) satisfying X ≈ WH. Two algorithms are studied and compared. These methods rely on a fundamental boundedness property of NMF which we propose and prove. This new property also provides a natural normalization scheme that eliminates the bias of factor matrices. Experiments on both synthetic and real world datasets are conducted to show the competency and effectiveness of BMF. 1.
Solving Consensus and Semi%2Dsupervised Clustering Problems Using Nonnegative Matrix Factorization.

Adaptive dimension reduction using discriminant analysis and K%2Dmeans clustering.
We combine linear discriminant analysis (LDA) and K-means clustering into a coherent framework to adaptively select the most discriminative subspace. We use K-means clustering to generate class labels and use LDA to do subspace selection. The clustering process is thus integrated with the subspace selection process and the data are then simultaneously clustered while the feature subspaces are selected. We show the rich structure of the general LDA-Km framework by examining its variants and their relationships to earlier approaches. Extensive experimental results on real-world datasets show the effectiveness of our approach. 1.
Finding Hotspots in Document Collection.

A learning framework using Green%27s function and kernel regularization with application to recommender system.

Nonnegative Matrix Factorization and Probabilistic Latent Semantic Indexing Equivalence Chi%2DSquare Statistic

Biclustering Protein Complex Interactions with a Biclique Finding Algorithm.

Biclustering Protein Complex Interactions with a Biclique Finding Algorithm.

The Relationships Among Various Nonnegative Matrix Factorization Methods for Clustering.
The nonnegative matrix factorization (NMF) has been shown recently to be useful for clustering. Various extensions of NMF have also been proposed. In this paper we present an overview and theoretically analyze the relationships among them. In addition, we clarify previously unaddressed issues, such as NMF normalization, cluster posterior probabilty, and NMF algoritm convergence rate. Experiments are also conducted to empirically evaluate and compare various factorization methods.
R1%2DPCA rotational invariant L1%2Dnorm principal component analysis for robust subspace factorization.

Supernova Recognition Using Support Vector Machines.
We introduce a novel application of Support Vector Machines (SVMs) to the problem of identifying potential supernovae using photometric and geometric features computed from astronomical imagery. The challenges of this supervised learning application are significant: 1) noisy and corrupt imagery resulting in high levels of feature uncertainty, 2) features with heavy-tailed, peaked distributions, 3) extremely imbalanced and overlapping positive and negative data sets, and 4) the need to reach high positive classification rates, i.e. to find all potential supernovae, while reducing the burdensome workload of manually examining false positives. High accuracy is achieved via a sign-preserving, shifted log transform applied to features with peaked, heavy-tailed distributions. The imbalanced data problem is handled by oversampling positive examples, selectively sampling misclassified negative examples, and iteratively training multiple SVMs for improved supernova recognition on unseen test data. We present crossvalidation results and demonstrate the impact on a largescale supernova survey that currently uses the SVM decision value to rank-order 600,000 potential supernovae each night. 1.
Orthogonal nonnegative matrix t%2Dfactorizations for clustering.

NMF and PLSI equivalence and a hybrid algorithm.

PSoL a positive sample only learning algorithm for finding non%2Dcoding RNA genes.

Dynamic Cluster Formation Using Level Set Methods.

Transitive closure and metric inequality of weighted graphs detecting protein interaction modules using cliques.
Transitive closure and metric inequality of weighted
A Multi%2DLevel Approach to SCOP Fold Recognition.
The classification of proteins based on their structure can play an important role in the deduction or discovery of protein function. However, the relatively low number of solved protein structures and the unknown relationship between structure and sequence requires an alternative method of representation for classification to be effective. Furthermore, the large number of potential folds causes problems for many classification strategies, increasing the likelihood that the classifier will reach a local optima while trying to distinguish between all of the possible structural categories. Here we present a hierarchical strategy for structural classification that first partitions proteins based on their SCOP class before attempting to assign a protein fold. Using a well-known dataset derived from the 27 most-populated SCOP folds and several sequence-based descriptor properties as input features, we test a number of classification methods, including Naïve Bayes and Boosted C4.5. Our strategy achieves an average fold recognition of 74%, which is significantly higher than the 56-60 % previously reported in the literature, indicating the effectiveness of a multi-level approach. 1
Nonnegative Lagrangian Relaxation of K%2DMeans and Spectral Clustering.

A Probabilistic Approach for Optimizing Spectral Clustering.
Spectral clustering enjoys its success in both data clustering and semisupervised learning. But, most spectral clustering algorithms cannot handle multi-class clustering problems directly. Additional strategies are needed to extend spectral clustering algorithms to multi-class clustering problems. Furthermore, most spectral clustering algorithms employ hard cluster membership, which is likely to be trapped by the local optimum. In this paper, we present a new spectral clustering algorithm, named “Soft Cut”. It improves the normalized cut algorithm by introducing soft membership, and can be efficiently computed using a bound optimization algorithm. Our experiments with a variety of datasets have shown the promising performance of the proposed clustering algorithm. 1
Dynamic Cluster Formation Using Level Set Methods.

Cluster Aggregate Inequality and Multi%2Dlevel Hierarchical Clustering.

Identification of Functional Modules in Protein Complexes via Hyperclique Pattern Discovery.

2%2DDimensional Singular Value Decomposition for 2D Maps and Images.

On the Equivalence of Nonnegative Matrix Factorization and Spectral Clustering.
Abstract Current nonnegative matrix factorization (NMF) dealswith X = F GT type. We provide a systematic analysisand extensions of NMF to the symmetric W = HHT,and the weighted W = HSHT. We show that (1) W = HHT is equivalent to Kernel K-means cluster-ing and the Laplacian-based spectral clustering. (2) X = F GT is equivalent to simultaneous clustering ofrows and columns of a bipartite graph. Algorithms are given for computing these symmetric NMFs.
Comparative mapping of sequence%2Dbased and structure%2Dbased protein domains.

Evolving Feature Selection.
We describe an evolutionary approach to active vision systems for dynamic feature selection. After summarizing recent work on evolution of a simulated active retina for complex shape discrimination, we describe in detail experiments that extend this approach to an all-terrain mobile robot equipped with a mobile camera. We show that evolved robots are capable of selecting simple visual features and actively maintaining them on the same retinal position, which largely simplifies the “recognition ” task, in order to generate efficient navigation trajectories with an extremely simple neural control system. Analysis of evolved solutions indicates that robots develop a simple
Feature Selection Based on Mutual Information Criteria of Max%2DDependency
Abstract—Feature selection is an important problem for pattern classification systems. We study how to select good features according to the maximal statistical dependency criterion based on mutual information. Because of the difficulty in directly implementing the maximal dependency condition, we first derive an equivalent form, called minimal-redundancy-maximal-relevance criterion (mRMR), for first-order incremental feature selection. Then, we present a two-stage feature selection algorithm by combining mRMR and other more sophisticated feature selectors (e.g., wrappers). This allows us to select a compact set of superior features at very low cost. We perform extensive experimental comparison of our algorithm and other methods using three different classifiers (naive Bayes, support vector machine, and linear discriminate analysis) and four different data sets (handwritten digits, arrhythmia, NCI cancer cell lines, and lymphoma tissues). The results confirm that mRMR leads to promising improvement on feature selection and classification accuracy. Index Terms—Feature selection, mutual information, minimal redundancy, maximal relevance, maximal dependency, classification. 1
CPL6 The New Extensible

Coupling Multicomponent Models with MPH on Distributed Memory Computer Architectures.


Term norm distribution and its effects on Latent Semantic Indexing.


A probabilistic model for Latent Semantic Indexing.
Dimension reduction methods, such as Latent Semantic Indexing (LSI), when applied to semantic space built upon text collections, improve information retrieval, information filtering and word sense disambiguation. A new dual probability model based on the similarity concepts is introduced to provide deeper understanding of LSI. Semantic associations can be quantitatively characterized by their statistical significance, the likelihood. Semantic dimensions containing redundant and noisy information can be separated out and should be ignored because their contribution to the overall statistical significance is negative. LSI is the optimal solution of the model. The peak in likelihood curve indicates the existence of an intrinsic semantic dimension. The importance of LSI dimensions follows the Zipf-distribution, indicating that LSI dimensions represent the latent concepts. Document frequency of words follow the Zipf distribution, and the number of distinct words follows log-normal distribution. Experiments on five standard document collections confirm and illustrate the analysis.
Positive Sample Only Learning %28PSOL%29 for Predicting RNA Genes in E. coli.

Contraction Graphs for Representation and Analysis of RNA Secondary Structure.

K%2Dmeans clustering via principal component analysis.
Principal component analysis (PCA) is a widely used statistical technique for unsupervised dimension reduction. K-means clustering is a commonly used data clustering for unsupervised learning tasks. Here we prove that principal components are the continuous solutions to the discrete cluster membership indicators for K-means clustering. Equivalently, we show that the subspace spanned by the cluster centroids are given by spectral expansion of the data covariance matrix truncated at K − 1 terms. These results indicate that unsupervised dimension reduction is closely related to unsupervised learning. On dimension reduction, the result provides new insights to the observed effectiveness of PCA-based data reductions, beyond the conventional noise-reduction explanation. Mapping data points into a higher dimensional space via kernels, we show that solution for Kernel K-means is given by Kernel PCA. On learning, our results suggest effective techniques for K-means clustering. DNA gene expression and Internet newsgroups are analyzed to illustrate the results. Experiments indicate that newly derived lower bounds for K-means objective are within 0.5-1.5 % of the optimal values. 1.
Linearized cluster assignment via spectral ordering.
Spectral clustering uses eigenvectors of the Laplacian of the similarity matrix. They are most conveniently applied to 2-way clustering problems. When applying to multi-way clustering, either the 2-way spectral clustering is recursively applied or an embedding to spectral space is done and some other methods are used to cluster the points. Here we propose and study a K-way cluster assignment method. The method transforms the problem to find valleys and peaks of a 1-D quantity called cluster crossing, which measures the symmetric cluster overlap across a cut point along a linear ordering of the data points. The method can either determine K clusters in one shot or recursively split a current cluster into several smaller ones. We show that a linear ordering based on a distance sensitive objective has a continuous solution which is the eigenvector of the Laplacian, showing the close relationship between clustering and ordering. The method relies on the connectivity matrix constructed as the truncated spectral expansion of the similarity matrix, useful for revealing cluster structure. The method is applied to newsgroups to illustrate introduced concepts; experiments show it outperforms the recursive 2-way clustering and the standard K-means clustering. 1.
Integrating Program Component Executables on Distributed Memory Architectures via MPH.

Cluster Structure of K%2Dmeans Clustering via Principal Component Analysis.

K%2Dnearest%2Dneighbor consistency in data clustering incorporating local information into global optimization.

Principal Component Analysis and Effective K%2DMeans Clustering.
Abstract. The widely adopted K-means clustering algorithm uses a sum of squared error objective function. A detailed analysis shows the close relationship between K-means clustering and principal component analysis (PCA) which is extensively utilized in unsupervised dimension reduction. We prove that the continuous solutions of the discrete K-means clustering membership indicators are the data projections on the principal directions (principal eigenvectors of the covariance matrix). New lower bounds for K-means objective function are derived, which relate directly to the eigenvalues of the covariance matrix. Experiments on Internet newsgroups indicate that the new bounds are within 0.5-1.5 % of the optimal values, and that PCA provides an effective solution for the K-means clustering. 1 Principal Component Analysis Principal component analysis (PCA)[5] in multivariate statistics is widely adopted as an effective unsupervised dimension reduction method and is extended in many different directions. The main justification of dimension reduction is that PCA uses singular value decomposition (SVD) which gives the best low rank approximation to original data in L2 norm due to Eckart-Young theorem. However, this essentially noise reduction perspective alone is inadequate to explain the effectiveness of PCA. In this paper, we provide a new perspective of PCA based on its close relationship with the K-means clustering algorithm. We show that the principal components are actually relaxed cluster membership indicators. Some background on PCA. The original n data points in m-dimensional space is contained in the data matrix (x1,  ·  · ·, xn)  = X. In general data is not centered around the origin. We define the centered data matrix Y = (y1,  ·  · ·, yn), where yi = xi − ¯x and ¯x = � i xi/n. The covarance matrix is given by S = � i (xi − ¯x)(xi −
Minimum Redundancy Feature Selection from Microarray Gene Expression Data.
Motivation. How to selecting a small subset out of the thousands of genes in microarray data is important for accurate classification of phenotypes. Widely used methods typically rank genes according to their differential expressions among phenotypes and pick the top-ranked genes. We observe that feature sets so obtained have certain redundancy and study methods to minimize it. Results. We propose a minimum redundancy – maximum relevance (MRMR) feature selection framework. Genes selected via MRMR provide a more balanced coverage of the space and capture broader characteristics of phenotypes. They lead to significantly improved class predictions in extensive experiments on 5 gene expression data sets: NCI,

Structure Search and Stability Enhancement of Bayesian Networks.

Data Clustering Principal Components%2C Hopfield and Self%2DAggregation Networks.


Unsupervised Feature Selection Via Two%2Dway Ordering in Gene Expression Analysis.

Cluster merging and splitting in hierarchical clustering algorithms.
Hierarchical clustering constructs a hierarchy of clusters by either repeatedly merging two smaller clusters into a larger one or splitting a larger cluster into smaller ones. The crucial step is how to best select the next cluster(s) to split or merge. Here we provide a comprehensive analysis of selection methods and propose several new methods. We perform extensive clustering experiments to test 8 selection methods, and find that the average similarity is the best method in divisive clustering and the MinMax linkage is the best in agglomerative clustering. Cluster balance is a key factor to achieve good performance. We also introduce the concept of objective function saturation and clustering target distance to e#ectively assess the quality of clustering.
Adaptive dimension reduction for clustering high dimensional data.
It is well-known that for high dimensional data clustering, standard algorithms such as EM and the K-means are often trapped in local minimum. Many initialization methods were proposed to tackle this problem , but with only limited success. In this paper we propose a new approach to resolve this problem by repeated dimension reductions such that K-means or EM are performed only in very low dimensions. Cluster membership is utilized as a bridge between the reduced dimensional subspace and the original space, providing flexibility and ease of implementation. Clustering analysis performed on highly overlapped Gaussians, DNA gene expression profiles and internet newsgroups demonstrate the e#ectiveness of the proposed algorithm.
Unsupervised Learning Self%2Daggregation in Scaled Principal Component Space.

Analysis of gene expression profiles class discovery and leaf ordering.
Abstract We approach the class discovery and leaf ordering problems using spectral graph partitioning methodologies. For class discovery or clustering, we present a rain-max cut hierarchical clustering method and show it produces subtypes quite close to human expert labeling on the lymphoma dataset with 6 classes. On optimal leaf ordering for displaying the gene expression data, we present a sequential or- dering method that can be computed in O(tz 2) time which also preserves the cluster structure. We also show that the well known statistic methods such as F-statistic test and the principal component analysis are very useful in gene expression analysis.
MPI and OpenMP paradigms on cluster of SMP architectures the vacancy tracking algorithm for multi%2Ddimensional array transposition.
We investigate remapping multi-dimensional arrays on cluster of SMP architectures under OpenMP,  MPI, and hybrid paradigms. Traditional method of array transpose needs an auxiliary array of the same  size and a copy back stage. We recently developed an in-place method using vacancy tracking cycles.
Web document clustering using hyperlink structures.
With the exponential growth of information on the World Wide Web, there is great demand for developing efficient and effective methods for organizing and retrieving the information available. Document clustering plays an important role in information retrieval and taxonomy management for the World Wide Web and remains an interesting and challenging problem in the field of web computing. In this paper we consider document clustering methods exploring textual information, hyperlink structure and co-citation relations. In particular, we apply the normalized-cut clustering method developed in computer vision to the task of hyperdocument clustering. We also explore some theoretical connections of the normalized-cut method to K-means method. We then experiment with normalized-cut method in the context of clustering query result sets for web search engines.
PageRank%2C HITS and a unified framework for link analysis.
Two popular webpage ranking algorithms are HITS and PageRank. HITS emphasizes mutual reinforcement between authority and hub webpages, while PageRank emphasizes hyperlink weight normalization and web surfing based on random walk models. We systematically generalize /combine these concepts into a unified framework. The ranking framework contains a large algorithm space
An Evaluation of MPI and OpenMP Paradigms for Multi%2DDimensional Data Remapping.

Web document clustering using hyperlink structures.
With the exponential growth of information on the World Wide Web, there is great demand for developing efficient and effective methods for organizing and retrieving the information available. Document clustering plays an important role in information retrieval and taxonomy management for the World Wide Web and remains an interesting and challenging problem in the field of web computing. In this paper we consider document clustering methods exploring textual information, hyperlink structure and co-citation relations. In particular, we apply the normalized-cut clustering method developed in computer vision to the task of hyperdocument clustering. We also explore some theoretical connections of the normalized-cut method to K-means method. We then experiment with normalized-cut method in the context of clustering query result sets for web search engines.
Bipartite Graph Partitioning and Data Clustering.
Many data types arising from data mining applications can be modeled as bipartite graphs, examples include terms and documents in a text corpus, customers and purchasing items in market basket analysis and reviewers and movies in a movie recommender system. In this paper, we propose a new data clustering method based on partitioning the underlying bipartite graph. The partition is constructed by minimizing a normalized sum of edge weights between unmatched pairs of vertices of the bipartite graph. We show that an approximate solution to the minimization problem can be obtained by computing a partial singular value decomposition (SVD) of the associated edge weight matrix of the bipartite graph. We point out the connection of our clustering algorithm to correspondence analysis used in multivariate analysis. We also briefly discuss the issue of assigning data objects to multiple clusters. In the experimental results, we apply our clustering algorithm to the problem of document clustering to illustrate its effectiveness and efficiency.
A Min%2Dmax Cut Algorithm for Graph Partitioning and Data Clustering.
An important application of graph partitioning is data clustering using a graph model | the pairwise similarities between all data objects form a weighted graph adjacency matrix that contains all necessary information for clustering. Here we propose a new algorithm for graph partition with an objective function that follows the min-max clustering principle. The relaxed version of the optimization of the min-max cut objective function leads to the Fiedler vector in spectral graph partition. Theoretical analyses of min-max cut indicate that it leads to balanced partitions, and lower bonds are derived. The min-max cut algorithm is tested on newsgroup datasets and is found to outperform other current popular partitioning/clustering methods. The linkagebased re nements in the algorithm further improve the quality of clustering substantially. We also demonstrate that the linearized search order based on linkage di erential is better than that based on the Fiedler vector, providing another e ective partition method.
Automatic Topic Identification Using Webpage Clustering.
Grouping webpages into distinct topics is one way to organize the large amount of retrieved information on the web. In this paper, we report that based on similarity metric which incorporates textual information, hyperlink structure and co-citation relations, an unsupervised clustering method can automatically and effectively identify relevant topics, as shown in experiments on several retrieved sets of webpages. The clustering method is a state-of-art spectral graph partitioning method based on normalized cut criterion first developed for image segmentation.

A spectral method to separate disconnected and nearly%2Ddisconnected web graph components.
Separation of connected components from a graph with disconnected graph components mostly use breadth-first search (BFS) or depth-first search (DFS) graph algorithms. Here we propose a new algebraic method to separate disconnected and nearly-disconnected components. This method is based on spectral graph partitioning, following a key observation that disconnected components will show up, after properly sorted, as step-function like curve in the lowest eigenvectors of the Laplacian matrix of the graph. Following an perturbative analysis framework, we systematically analyzed the graph structures, rst on the disconnected subgraph case, and second on the e ects of adding edges sparsely connecting di erent subgraphs as a perturbation. Several new results are derived, providing insights to spectral methods and related clustering objective function. Examples are given illustrating the concepts and results our methods. Comparing to the standard graph algorithms, this method has the same O(jEj + jV jlog(jV j)) complexity, but is easier to implement (using readily available eigensolvers). Further more the method can easily identify articulation points and bridges on nearly-disconnected graphs. Segmentation of a real example of Web graph for query amazon is given. We found that each disconnected or nearly-disconnected components forms a cluster on a clear topic.
Spectral Relaxation for K%2Dmeans Clustering.
The popular K-means clustering partitions a data set by minimizing a sum-of-squares cost function. A coordinate descend method is then used to find local minima. In this paper we show that the minimization can be reformulated as a trace maximization problem associated with the Gram matrix of the data vectors. Furthermore, we show that a relaxed version of the trace maximization problem possesses global optimal solutions which can be obtained by computing a partial eigendecomposition of the Gram matrix, and the cluster assignment for each data vectors can be found by computing a pivoted QR decomposition of the eigenvector matrix. As a by-product we also derive a lower bound for the minimum of the sum-of-squares cost function.
A ghost cell expansion method for reducing communications in solving PDE problems.
In solving Partial Differential Equations, such as the Barotropic equations in ocean models, on  Distributed Memory Computers, finite difference methods are commonly used. Most often, processor  subdomain boundaries must be updated at each time step. This boundary update process involves  many messages of small sizes, therefore large communication overhead. Here we propose a new approach  which expands the ghost cell layers and thus updates boundaries much less frequently ---  reducing total message volume and groupping small messages into bigger ones. Together with a technique  for eliminating diagonal communications, the method speedup communication substantially,  upto 170%. We explain the method and implementation in details, provide systematic timing results  and performance analysis on the Cray T3E and IBM SP.
Multi%2Dclass protein fold recognition using support vector machines and neural networks.
Motivation: Protein fold recognition is an important approach to structure discovery without  relying on sequence similarity. We study this approach with new multi-class classication  methods and examined many issues important for a practical recognition system.  Results: Most current discriminative methods for protein fold prediction use the one-againstothers  method, which has the well-known \False Positives&#034; problem. We investigated two  new methods: the unique one-against-others and the all-against-all methods. Both improve  prediction accuracy by 14-110% on a dataset containing 27 SCOP folds. We used the Support  Vector Machine and the Neural Network learning methods as base classiers. SVM converges  fast and leads to high accuracy. When scores of multiple parameter datasets are combined,  majority voting reduces noise and increases recognition accuracy. We examined many issues  involved with large number of classes, including dependencies of prediction accuracy on the  number of folds and on the number of representatives in a fold. Overall, recognition systems  achieve 56% fold prediction accuracy on a protein test dataset, where most of the proteins  have below 25% sequence identity with the proteins used in training.  Contact: chqding@lbl.gov, ildubchak@lbl.gov  Supplementary Information: The protein parameter datasets used in this paper is available  online (http://www.nersc.gov/    cding/protein).  Keywords: protein fold recognition, protein structure, multi-class classication, support  vection machines, neural networks.    To whom correspondence should be addressed.  1 
Bipartite graph partitioning and data clustering
Many data types arising from data mining applications can be modeled as bipartite graphs, examples include terms and documents in a text corpus, customers and purchasing items in market basket analysis and reviewers and movies in a movie recommender system. In this paper, we propose a new data clustering method based on partitioning the underlying bipartite graph. The partition is constructed by minimizing a normalized sum of edge weights between unmatched pairs of vertices of the bipartite graph. We show that an approximate solution to the minimization problem can be obtained by computing a partial singular value decomposition (SVD) of the associated edge weight matrix of the bipartite graph. We point out the connection of our clustering algorithm to correspondence analysis used in multivariate analysis. We also briefly discuss the issue of assigning data objects to multiple clusters. In the experimental results, we apply our clustering algorithm to the problem of document clustering to illustrate its effectiveness and efficiency.

High Performance Computations for Large Scale Simulations of Subsurface Multiphase Fluid and Heat Flow.
TOUGH2 is a widely used reservoir simulator for solving subsurface flow related problems such as nuclear waste geologic isolation, environmental remediation of soil and groundwater contamination, and geothermal reservoir engineering. It solves a set of coupled mass and energy balance equations using a finite volume method. This contribution presents a parallel version of TOUGH2. The parallel implementation first partitions the unstructured computational domain. For each time step, a set of coupled non-linear equations is solved with Newton iteration. In each Newton step, a Jacobian matrix is calculated and an ill-conditioned non-symmetric linear system is solved using a preconditioned iterative solver. Communication is required for convergence tests and data exchange across partitioning borders. Parallel performance results on Cray T3E-900 are presented for two real application problems arising in the Yucca Mountain nuclear waste site study. The execution time is reduced from 7504 seconds on two processors to 126 seconds on 128 processors for a 2D problem involving 52,752 equations. For a larger 3D problem with 293,928 equations the time decreases from 10055 seconds on 16 processors to 329 seconds on 512 processors.
Using Accurate Arithmetics to Improve Numerical Reproducibility and Stability in Parallel Applications.

Using accurate arithmetics to improve numerical reproducibility and stability in parallel applications.

Parallel Algorithms for 1D FFTs on Real Numbers.

A Similarity%2Dbased Probability Model for Latent Semantic Indexing.
A dual probability model is constructed for the Latent Semantic Indexing (LSI) using the cosine similarity measure. Both the document-document similarity matrix and the term-term similarity matrix naturally arise from the maximum likelihood estimation of the model parameters, and the optimal solutions are the latent semantic vectors of of LSI. Dimensionality reduction is justified by the statistical significance of latent semantic vectors as measured by the likelihood of the model. This leads to a statistical criterion for the optimal semantic dimensions, answering a critical open question in LSI with practical importance. Thus the model establishes a statistical framework for LSI. Ambiguities related to statistical modeling of LSI are clarified.
High Performance Fortran for practical scientific algorithms An up%2Dto%2Ddate evaluation.
. A suite of HPF coding examples of practical scientific algorithms are examined in detail, with the idea that on these simple but non-trivial examples, we can fairly well understand issues related to different data distributions, different parallel constructs, and different programming styles (static vs dynamic allocations). Coding examples include 2D stencils solution of PDEs, N-body problem, LU factorization, several vector/matrix library routines, 2D and 3D array redistribution. Performances of HPF codes are compared to hand-written Fortran codes with message passing library. From 1997 to 1998, HPF compilers are improved significantly such that HPF codes perform as well as Fortran+MPI codes for all the examples investigated here. However, many important peculiarities of HPF coding still exist.  Keywords: HPF, Distributed-memory architecture, Parallel programming language, MPI, Stencils computation, N-body problem, LU factorization, Array redistribution, FFT.  1. Introduction  High ...
Atmosperic Data Assimilation on Distributed%2DMemory Parallel Supercomputers.

Evaluations of HPF for Practical Scientific Algorithms on T3E.
. HPF coding examples of practical scientific algorithms are examined in detail, with the idea that on these simple but non-trivial examples, we can fairly well understand issues related to different data distributions, different parallel constructs, and different programming styles (static vs dynamic allocations). Coding examples include 2D stencils solution of PDEs, N-body problem, LU factorization, several vector/matrix library routines, 2D and 3D array redistribution.The performances of HPF codes are close to hand-written message passing MPI codes, for LU factorization, vector/matrix routines, array redistributions. But for less regular data/communication patterns, the stencils calculation and the N-body problem, HPF codes perform considerably less efficient, about 2-4 times slower. Scaling of HPF codes is not as good as MPI codes. Some of the HPF codes performances are highly inconsistent, i.e., minor change of code could results in factor of 10 change in performance. Many peculia...
An Element%2DBased Concurrent Partitioner for Unstructured Finite Element Meshes.
Abstract. A concurrent partitioner for partitioning unstructured finite element meshes on distributed memory architectures is developed. The partitioner uses an element-based partitioning strategy. Its main advantage over the more conventional node-based partitioning strategy is its modular programing approach to the development of parallel applications. The partitioner first partitions element centroids using a recursive inertial bisection algorithm. Elements and nodes then migrate according to the partitioned centroids, using a data request communication template for unpredictable incoming messages. Our scalable implementation is contrasted to a non-scalable implementation which is a straightforward parallelization of a sequential partitioner. The algorithms adopted in the partitioner scale logarithmically, as confirmed by actual timing measurements on the Intel Delta on up to 512 processors for scaled size problems. 1.
A general purpose sparse matrix parallel solvers package.
Introduction  One of the common problems in scientific and  engineering computations is the constrcution and solution  of sparse linear systems arising from solving partial  differential equations based on unstructured grids[1].  Many such examples occur in analysis by finite element,  finite difference and finite volume methods. As the scale  and complexity of the calculations grow, massively parallel  computers are increasingly widely used in these calculations.  .  Existing parallel sparse linear system solvers can  be classified into to two distinctive classes(see [2] and  references therein). One is the inerative conjugate-gradient  type of solvers where the key parallel part is the  matrix-vector product([2,3,4]); the other is parallel  Cholesky factorization solvers using column/row based  matrix distributions[5,6,2].  N  However, these solvers mostly are restricted to positive definite matrices. For a larger classs of symmetric complex matrix systems, fe
A General Purpose Sparse Matrix Parallel Solvers Package.
Introduction  One of the common problems in scientific and  engineering computations is the constrcution and solution  of sparse linear systems arising from solving partial  differential equations based on unstructured grids[1].  Many such examples occur in analysis by finite element,  finite difference and finite volume methods. As the scale  and complexity of the calculations grow, massively parallel  computers are increasingly widely used in these calculations.  .  Existing parallel sparse linear system solvers can  be classified into to two distinctive classes(see [2] and  references therein). One is the inerative conjugate-gradient  type of solvers where the key parallel part is the  matrix-vector product([2,3,4]); the other is parallel  Cholesky factorization solvers using column/row based  matrix distributions[5,6,2].  N  However, these solvers mostly are restricted to positive definite matrices. For a larger classs of symmetric complex matrix systems, fe
Slices A Scalable Partitioner for Finite Element Meshes.
A parallel partitioner for partitioning unstructured finite element meshes on distributed memory architectures is developed. The element based partitioner can handle mixtures of different element types. All algorithms adopted in the partitioner are scalable, including a communication template for unpredictable incoming messages, as shown in actual timing measurements. 1 Introduction  Partitioning a finite element mesh among the processors of a parallel supercomputer sets up the stage for the finite element analysis problem. The domain partition achieves load balance, preserves proper data locality and reduces communications during the solution of the problem. To handle large meshes and to avoid excessive IO, our partitioner partitions the mesh concurrently on the parallel computer, in contrast to most existing partitioners which partition mesh on a sequential computer and then download the partitioned mesh to a distributed memory computer.  2 Mesh Decomposition  The element-based parti...
A Portable 3D FFT Package for Distributed%2DMemory Parallel Architectures.
A parallel algorithm for 3D FFTs is implemented as a series of local 1D FFTs combined with data transposes. This allows the use of vendor supplied (often fully optimized) sequential 1D FFTs. The FFTs are carried out in-place by using an inplace data transpose across the processors. 1 Introduction  Multi-dimensional FFTs are used frequently in engineering and scientific calculations, especially in image processing. Parallel implementations of FFT generally follow two approaches. One is the binary-exchange approach[1,2], where data exchanges take place in all pairs of processors with processor numbers differing by one bit. Another one is the transpose approach[2] for multi-dimensional FFTs, where a 3D FFT is carried out in 3 successive 1D local sequential FFTs with data transposes occurring in between. Inter-processor communication only take place in these data transpose. One advantage of this approach is that we can use the vendor-supplied 1D FFTs, which are often fully optimized. Furth...
Monte Carlo simulations of Quantum systems on massively parallel computers.

